package com.algorithm.search;

import com.google.common.base.Strings;

/**
 * @program: study
 * @className: Tire
 * @description: 字典树
 * 1. 目前只支持小写字母
 * @author: kukuxiahuni
 * @create: 2020-01-16 19:25
 * @version: v1.0
 **/
public class Tire {

    /**
     * 头结点值为空
     */
    private final Node header = new Node(' ');

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 7:47 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 7:47 下午
     **/
    public static void main(String[] args) {
        Tire tire = new Tire();
        String[] strings = {"how", "hi", "her", "hello", "so", "see"};

        for (String str : strings) {
            tire.insert(str);
        }

        System.out.println(tire.find("ho"));

    }

    /**
     * 功能描述: 向字典树中插入单词
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 7:31 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 7:31 下午
     **/
    public void insert(String word) {
        if (Strings.isNullOrEmpty(word)) {
            return;
        }

        Node p = header;
        word = word.toLowerCase();
        for (int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            Node node = p.children[index];
            if (node == null) {
                Node newNode = new Node(word.charAt(i));
                p.children[index] = newNode;
            }
            p = p.children[index];
        }
        p.isEnd = true;
    }

    /**
     * 功能描述: 查找字符串是否存在
     * 1. 注意查找字符串，表示字符串最终以叶子节点结尾
     * 2. 查找前缀的话，无需判定叶子节点
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 7:42 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 7:42 下午
     **/
    public boolean find(String pattern) {

        if (Strings.isNullOrEmpty(pattern)) {
            return false;
        }

        pattern = pattern.toLowerCase();

        Node p = this.header;

        for (int i = 0; i < pattern.length(); ++i) {
            int index = pattern.charAt(i) - 'a';
            Node node = p.children[index];
            if (node == null) {
                return false;
            }

            p = node;
        }

        return p.isEnd;

    }


    /**
     * 功能描述: 字典树节点类
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/16 7:28 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/16 7:28 下午
     **/
    private final static class Node {
        /**
         * 节点值
         */
        char value;
        /**
         * 子节点
         */
        Node[] children = new Node[26];
        /**
         * 单词是否结束
         */
        boolean isEnd;

        public Node(char value) {
            this.value = value;
        }
    }


}
